Wireless Local Area Network (WLAN) protocols such as those based on the IEEE 802.11 standards or based on the Bluetooth™ standard are designed to recreate the high Quality of Service (QoS) that is typically supplied in wired networks that use standard LAN protocols such as Ethernet. That high QoS includes uninterrupted network connections, high throughput and reliable delivery of data. Maintaining that QoS in a WLAN is more difficult than in a wired network however because wireless connections exhibit negative characteristics such as “fast fading,” “shadow fading” and long-time-scale variations that are not found in wired networks. “Fast fading” concerns rapid fluctuations in signal integrity on the order of milliseconds due to various types of interference; “shadow fading” concerns relatively slower fluctuations on the order of hundreds of milliseconds; and long-time-scale variations concern even slower fluctuations in signal integrity often due to movement of a user terminal such as a Personal Digital Assistant (PDA). Maintaining a high QoS in a WLAN therefore requires vigilant attention to error detection and correction and also requires careful monitoring of the conditions of the wireless link.
Despite the above negative characteristics WLANs are frequently preferred over wired LANs for numerous reasons. For example, with WLANs it is easy to use “ad hoc” networks that can be quickly assembled and torn down; WLANs may also be more economical when compared with the high cost of infrastructure wiring; and users often demand user terminal mobility such as with lap top computers and PDAs.
The IEEE 802.11 standard concerns the operation of a network's Media Access Control (MAC) layer. The MAC layer resides just above a network's Physical (PHY) layer and is responsible for controlling access to the wireless channel. The MAC receives MAC Service Data Units (MSDUs) from the higher layers. MSDU's may be fragmented into smaller MAC Protocol Data Units (MPDUs), which are then transported between network stations across the wireless medium. Network stations are devices connected to the network which may be mobile, portable, or stationary. MPDUs are transmitted between network stations using a carrier sense multiple access with collision avoidance (CSMA/CA) protocol. Collision detection such as that used in the Ethernet protocol cannot be used in wireless transmissions, because when a wireless station is transmitting it cannot hear other stations on the network as its own signal will interfere with any received signal. The IEEE 802.11 standard refers to the above method of channel access as the Distributed Co-Ordination Function (DCF).
A second channel access method is provided in networks where an Access Point (AP) is present. This method, referred to as the Point Co-ordination Function (PCF), uses polling to provide access to the wireless medium. The AP constructs a polling list that determines the order in which the stations within the network will be polled.
In an IEEE 802.11 network, stations are collected into a Basic Service Set (BSS). A BSS may comprise an ad hoc network where all stations in the network can communicate directly with all other stations. Alternatively a BSS may include an AP in which case it is called an infrastructure BSS. In an infrastructure BSS, all stations communicate exclusively through the AP. The AP is often connected to a wired LAN and therefore can significantly increase the range and resources available to a BSS.
Extensions to the existing IEEE 802.11 protocol will include the IEEE 802.11 (e) QoS extensions. These are based on both the CSMA/CA channel access method, and on the polling method. In an infrastructure BSS that is providing QoS, the AP must schedule all data downlinks to all stations in the BSS and all data uplinks from the stations to the AP. Optimizing such scheduling using a scheduling algorithm is often a complex process that requires consideration of numerous variables such as the specific QoS requirements of individual stations, fading disruptions, and the load of individual stations (i.e., the amount of data queued at a station waiting to be uplinked to the AP).
In a Bluetooth™ network, similar scheduling requirements exist. A Bluetooth™ piconet requires a MAC layer scheduling algorithm to schedule all uplinks and downlinks between a master node and all slave nodes in the piconet. For purposes of describing the present invention, APs or Masters are herein generically referred to as base stations; and nodes or stations are generically referred to as user terminals.
A base station may communicate with user terminals using explicit and implicit polls. User terminals are generally allowed to transmit data to the base station only if the base station polled the user terminal in an immediately preceding time slot. An explicit poll is when a base station has no data to download to a user terminal, but needs to inform the user terminal that it is free to uplink data to the base station. The base station therefore transmits a null frame (a frame that includes no data) to the user terminal, which tells the user terminal that it is free to uplink data. An implicit poll is when the base station downloads data to a user terminal and thereby implicitly informs the user terminal that it is free to uplink data immediately following the download.
Various methods of polling exist such as Round Robin polling where user terminals are polled cyclically one after another regardless of whether a user terminal has data to transmit or not. Round Robin polling is thus considered inefficient because bandwidth is wasted on idle user terminals even if other fully loaded user terminals require additional bandwidth.
Fair Exhaustive Polling is more efficient than Round Robin polling as it divides user terminals into two categories: active user terminals and inactive user terminals. The active user terminals are polled using a Round Robin technique; and the inactive user terminals are polled only intermittently to determine whether they should become active user terminals. Fair Exhaustive Polling more efficiently utilizes the limited bandwidth available to the network and is considered more fair because fully loaded user terminals are provided more time to transmit.
Numerous other algorithms exist that attempt to achieve fair and efficient polling. In algorithms designed to provide a probabilistic delay bound (i.e., a QoS requirement that places limits on how long data frame transmissions can be delayed) on an uplink channel, the base station requires information about the needed individual data stream bandwidth. However, by attempting to minimize channel access delay, most algorithms will result in an inefficient polling list. That is because there is a high probability of either multiple polls being sent per channel access opportunity effectively used, or polls arriving significantly earlier than the corresponding data frames.
There is therefore a need for an improved algorithm for estimating the individual stream bandwidth requirements of an uplink channel and for fairly and efficiently scheduling access to a wireless network's limited bandwidth. Further, there is a need to overcome the lack of accurate user terminal queue state information at a base station. QoS scheduling algorithms designed to employ queuing delay as the traffic metric are required to actively sample the individual queue delays. For an uplink stream, this must be reported back to the base station. Given that a realistic scheduling algorithm implementation must generate a polling list over a future scheduling window based on collected information, there is significant potential for inaccurate or delayed information resulting in poor network performance.